# coding: utf-8
# FIFO队列实现

#python自带的Queue
import Queue as Q

#先进先出
qu=Q.Queue(maxsize=10)
for i in range(5):
    qu.put(i)
print("Queue")
print(qu.get())
print(qu.get())
print("size:",qu.qsize())

#不管是List还是Tuple，第1个元素data[0]是优先级值，优先级值越小，优先级越高
pq=Q.PriorityQueue(maxsize=10)
pq.put([1,"apple",100])
pq.put([2,"pear",50])
pq.put([3,"peach",25])
print("PriorityQueue")
print(pq.get())
print(pq.get())
print("size:",pq.qsize())

#后进先出
qu=Q.LifoQueue(maxsize=10)
for i in range(5):
    qu.put(i)
print("LifoQueue")
print(qu.get())
print(qu.get())
print("size:",qu.qsize())

#使用栈记录迷宫路径
#迷宫(0表示可以通过，1表示不能通过，-1表示已走过，最外一层是城墙，起点是[1][1]，终点shi[8][8])
maze=[
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
#4个方向，返回一个Tuple
directions=[
    lambda x,y:(x-1,y),
    lambda x,y:(x+1,y),
    lambda x,y:(x,y-1),
    lambda x,y:(x,y+1)
]

#bfs对应队列（bfs找到的【第一条通路】一定是【最短的】！）
#记录路径：记录每个节点的父节点
def findPath(x1,y1,x2,y2):
    qu=Q.Queue(maxsize=150)
    parents={}
    maze[x1][y1]=-1
    qu.put((x1,y1))

    while not qu.empty():
        curPos=qu.get()
        if curPos[0]==x2 and curPos[1]==y2:
            #打印路径
            node=curPos
            path=[node]
            while parents.has_key("{0},{1}".format(node[0],node[1])):
                node=parents.get("{0},{1}".format(node[0],node[1]))
                path.append(node)
            #逆转列表
            path=path[::-1]
            print(path)
            return True
        for direct in directions:
            nextPos=direct(curPos[0],curPos[1])
            #如果孩子节点可以走
            if maze[nextPos[0]][nextPos[1]] == 0:
                key="{0},{1}".format(nextPos[0],nextPos[1])
                parents[key]=curPos
                maze[nextPos[0]][nextPos[1]]=-1
                qu.put(nextPos)
    print("找不到出口")
    return False

findPath(1,1,8,8)
